package com.wujunshen.algorithm.leetcode.basic;

import java.util.HashMap;
import java.util.Map;

import lombok.Data;
import lombok.Getter;
import lombok.NoArgsConstructor;
import lombok.Setter;
import lombok.extern.slf4j.Slf4j;

/**
 * @author frank woo(吴峻申) <br>
 *     email:<a href="mailto:frank_wjs@hotmail.com">frank_wjs@hotmail.com</a> <br>
 * @date 2022/7/2 17:59<br>
 */
@Data
@Slf4j
public class LRUCache {
  private int capacity;
  private int count;
  private Node dummyHead;
  private Node dummyTail;
  private Map<Integer, Node> hashMap;

  public LRUCache(int capacity) {
    this.capacity = capacity;
    this.count = 0;
    this.dummyHead = new Node(0, 0);
    this.dummyTail = new Node(0, 0);
    dummyHead.next = this.dummyTail;
    dummyTail.prev = this.dummyHead;
    hashMap = new HashMap<>();
  }

  public int get(int key) {
    Node node = hashMap.get(key);
    if (node == null) {
      return -1;
    }
    moveToHead(node);
    return node.getValue();
  }

  public void put(int key, int value) {
    Node node = hashMap.get(key);
    if (node == null) {
      Node newNode = new Node(key, value);
      hashMap.put(key, newNode);
      if (count < capacity) {
        addToHead(newNode);
        count++;
      } else {
        hashMap.remove(dummyTail.prev.key);
        deleteNode(dummyTail.prev);
        addToHead(newNode);
      }
    } else {
      node.setValue(value);
      moveToHead(node);
    }
  }

  private void moveToHead(Node node) {
    deleteNode(node);
    addToHead(node);
  }

  private void deleteNode(Node node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }

  private void addToHead(Node node) {
    node.next = dummyHead.next;
    node.next.prev = node;
    node.prev = dummyHead;
    dummyHead.next = node;
  }

  @Setter
  @Getter
  @NoArgsConstructor
  static class Node {
    private int key;
    private int value;
    private Node next;
    private Node prev;

    public Node(int key, int value) {
      this.key = key;
      this.value = value;
      this.next = null;
      this.prev = null;
    }

    @Override
    public String toString() {
      return "key is:" + key + ",value is:" + value;
    }
  }

  public static void main(String[] args) {
    LRUCache lruCache = new LRUCache(2);
    log.info("lruCache is:{}", lruCache);

    // 缓存是 {1=1}
    lruCache.put(1, 1);
    log.info("lruCache is:{}", lruCache);

    // 缓存是 {1=1, 2=2}
    lruCache.put(2, 2);
    log.info("lruCache is:{}", lruCache);

    // 返回 1
    int value = lruCache.get(1);
    log.info("value is:{}", value);

    // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
    lruCache.put(3, 3);
    log.info("lruCache is:{}", lruCache);

    // 返回 -1 (未找到)
    value = lruCache.get(2);
    log.info("value is:{}", value);

    // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
    lruCache.put(4, 4);
    log.info("lruCache is:{}", lruCache);

    // 返回 -1 (未找到)
    value = lruCache.get(1);
    log.info("value is:{}", value);

    // 返回 3
    value = lruCache.get(3);
    log.info("value is:{}", value);

    // 返回 4
    value = lruCache.get(4);
    log.info("value is:{}", value);
  }
}
